package com.justnow.offer;

import java.util.Arrays;

/**
 * @author justnow
 * Created on 2020-09-08
 * Description
 */
public class Solution56 {
    public int[][] merge(int[][] intervals) {
        // 先按照区间其实位置排序
        Arrays.sort(intervals, (x1, x2) -> x1[0] - x2[0]);
        // 需要返回的二维数组结果集，行数最大不超过length
        int[][] res = new int[intervals.length][2];
        // 进行定位
        int idx = -1;
        for (int[] interval : intervals) {
            // 如果结果数组为空，或者当前区间的起始位置 > 结果集最后一个区间的右边元素的值，
            // 说明不存在重叠的内容，直接将当前区间加入到结果数组中。
            if (idx == -1 || interval[0] > res[idx][1])
                res[++idx] = interval;
            // 不满足上述条件的话，说明存在重叠的地方，那么只判断结果集中的最后一个区间的右边元素
            // 和 当前区间的右边元素的最大值，从而合并重叠的区间
            else
                res[idx][1] = Math.max(res[idx][1], interval[1]);
        }
        return Arrays.copyOf(res, idx + 1);
    }
}
